\documentclass[E:/GsjzTle/main/main.tex]{subfiles}


\begin{document}

\begin{itemize}
\item
  可撤销并查集不支持路径压缩，只能按秩合并（所以要记得改 \(find\) 函数）
\item
  实现过程就是当两个数合并的时候把它们丢入栈中，等需要撤销的时候再从栈中拿出（通常搭配线段树时间分治使用）
\end{itemize}

\begin{lstlisting}
int far[N] , size[N];
int find(int x)
{
	if(x == far[x]) return x;
	return find(far[x]); // 不能用路径压缩！ 
}
void Union(int x , int y , stack<pii>&st)
{
	int tx = find(x) , ty = find(y);
	if(tx != ty) 
	{
		if(size[tx] > size[ty]) swap(tx , ty);
		st.push(make_pair(tx , ty));
		far[tx] = ty;
		size[ty] += size[tx];
	}
}
void Redo(stack<pii>&st)
{
	while(!st.empty())
	{
		pii u = st.top();
		st.pop();
		far[u.fi] = u.fi;
		size[u.se] -= size[u.fi];
	}
}
\end{lstlisting}

\end{document}
